package Leetcode.图;

import java.util.*;

/**
 * @ClassName 课程表
 * @since: 2023/9/9 09:43
 * @auth: kirito
 * @description:
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 *
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，
 * 其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 *
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 * 示例 2：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * 输出：false
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；
 * 并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 **/
public class 课程表 {

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ans = new int[numCourses];
        int index = 0;

        int[] indegrees = new int[numCourses];  // 存储每门课程的入度
        List<List<Integer>> adjacency = new ArrayList<>();  // 存储课程之间的依赖关系
        Queue<Integer> queue = new LinkedList<>();  // 用于拓扑排序的队列
        for (int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());

        // 获取每门课程的入度和依赖关系
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++;  // 课程cp[0]的入度加1
            adjacency.get(cp[1]).add(cp[0]);  // 课程cp[1]依赖于课程cp[0]
        }

        // 将入度为0的课程加入队列
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.add(i);
            }
        }

        // 进行拓扑排序
        while (!queue.isEmpty()) {
            int pre = queue.poll();  // 取出队首课程
            ans[index++] = pre;
            numCourses--;  // 已学习的课程数量减1
            for (int cur : adjacency.get(pre)) {  // 遍历当前课程的后续课程
                if (--indegrees[cur] == 0) {  // 将后续课程的入度减1，若入度为0，则加入队列
                    queue.add(cur);
                }
            }
        }

        return numCourses == 0 ? ans:new int[0];  // 若所有课程都学习完，则返回true，否则返回false
    }

    /**
     * 你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。
     *
     * 有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。
     * 先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。
     *
     * 你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。
     *
     * 返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。
     *
     * 示例 1：
     *
     * 输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
     * 输出：[false,true]
     * 解释：[1, 0] 数对表示在你上课程 0 之前必须先上课程 1。
     * 课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。
     * 示例 2：
     *
     * 输入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
     * 输出：[false,false]
     * 解释：没有先修课程对，所以每门课程之间是独立的。
     * 示例 3：
     *
     * 输入：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
     * 输出：[true,true]
     *
     * 实质上相较以上题目，就是在拓扑排序已有的基础上判断i是否在j之前，在的话就ture，否则false
     */
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        int[] indgree = new int[numCourses];
        boolean[][] isPre = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) {
            ++indgree[p[1]];
            graph[p[0]].add(p[1]);
        }
        Queue<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i < numCourses; ++i) {
            if (indgree[i] == 0) {
                queue.offer(i);
            }
        }
        // 当队列不为空时，继续处理队列中的课程
        while (!queue.isEmpty()) {
            // 从队列中取出一个当前可以学习的课程
            int cur = queue.poll();
            // 遍历当前课程的所有后续课程（依赖当前课程的其他课程）
            for (int ne : graph[cur]) {
                // 设置当前课程为后续课程的先修课程
                isPre[cur][ne] = true;
                // 更新所有课程到后续课程的先修关系
                // 如果课程i到当前课程有先修关系，或者课程i到后续课程有先修关系
                // 则课程i到后续课程也有先修关系
                for (int i = 0; i < numCourses; ++i) {
                    isPre[i][ne] = isPre[i][ne] | isPre[i][cur];
                }
                // 当前课程完成后，其后续课程的入度减少1
                --indgree[ne];
                // 如果后续课程的入度变为0，说明它所有的先修课程都已经被学习
                // 因此，可以将该课程加入队列，准备进行学习
                if (indgree[ne] == 0) {
                    queue.offer(ne);
                }
            }
        }

        List<Boolean> res = new ArrayList<Boolean>();
        for (int[] query : queries) {
            res.add(isPre[query[0]][query[1]]);
        }
        return res;
    }


    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();  // 存储课程之间的依赖关系
        for (int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());

        int[] flags = new int[numCourses];  // 用于标记课程的状态，0表示未访问，1表示正在访问，-1表示已完成访问

        for (int[] cp : prerequisites)
            adjacency.get(cp[1]).add(cp[0]);  // 课程cp[1]依赖于课程cp[0]

        for (int i = 0; i < numCourses; i++) {
            if (!dfs(adjacency, flags, i))  // 深度优先遍历判断是否存在环路依赖
                return false;
        }

        return true;  // 不存在环路依赖，可以完成所有课程的学习
    }

    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if (flags[i] == 1)  // 若当前课程正在访问，说明存在环路依赖，返回false
            return false;

        if (flags[i] == -1)  // 若当前课程已完成访问，直接返回true
            return true;

        flags[i] = 1;  // 标记当前课程为正在访问状态

        for (Integer j : adjacency.get(i)) {
            if (!dfs(adjacency, flags, j))  // 递归访问当前课程的后续课程
                return false;
        }

        flags[i] = -1;  // 标记当前课程为已完成访问状态

        return true;
    }

}
